<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>无标题文档</title>
<script>
/***************************************
**	链表分为单向链表和双向链表
**	双向链表中，链接是双向的：
**	一个链向下一个元素next，
**	一个链向前一个元素prev
**
**	循环链表也分为单向循环链表和双向循环链表
**	单向循环链表末尾的元素的next指向head元素
**	双向循环链表末尾元素的next指向head元素，
**	head元素的prev指向末尾的元素
***************************************/

//	创建单向链表
function LinkedList(){
	
	var Node = function(element){
		this.element = element;
		this.next = null;
	}
	
	var length = 0;
	var head = null;
	
	//	向链表尾部追加元素
	this.appdend = function(element){
		var node = new Node(element);
		var current;
		if (head == null){
			head = node;
		}else {
			current = head;
			
			while (current.next){
				current = current.next;
			}
			current.next = node;
		}
		length ++;
	}
	
	//	向链表的特定位置添加元素,添加成功返回true
	this.insert = function(position, element){
		if (position>-1 && position<length){
			var node = new Node(element);
			var current = head;
			var previous ;
			var index = 0;
			
			if (position == 0){
				node.next = current;
				head = node;
			}else{
				while (index++ < position){
					previous = current;
					current = current.next;	
				}
				node.next = current;
				previous.next = node;
			}
			
			length++;
			return true;
		}else{
			return false;
		}
	}
	
	//	移除链表中的某一项
	this.remove = function(element){
		var index = this.indexof(element);
		return this.removeAt(index);
	}
	
	//	移除链表中特定位置的某一项，返回被移除的元素
	this.removeAt = function(position){
		if (position>-1 && position<length){
			var current = head;
			var previous;
			var index = 0;
			if (position == 0){
				head = current.next;
			}else {
				
				while (index++ < position){
					previous = current;
					current = current.next;	
				}
				previous.next = current.next;
				
			}
			length--;
			
			return current.element;
		}else {
			return null;
		}
	}
	
	//	返回元素在链表中的索引，如果链表中没有该元素则返回-1
	this.indexof = function(element){
		var current = head;
		var index = 0;
		while (current){
			if (element === current.element){
				return index;
			}
			index++;
			current = current.next;
		}
		return -1;
	}
	
	//	判断链表是否为空
	this.isEmpty = function(){
		return length==0;
	}
	
	//	返回链表中元素的个数
	this.size = function(){
		return length;
	}
	
	//	返回链表中第一个元素
	this.getHead = function(){
		return head;
	}
	
	this.tostring = function(){
		var current = head;
		var string = '';
		while (current){
			string += current.element + " ";
			current = current.next;
		}
		return string;
	}
	
	this.println = function(){
		console.log(this.tostring());
	}
}

var linkedList = new LinkedList();
linkedList.appdend("2");
linkedList.appdend("80");
linkedList.insert(1,"a");
console.log(linkedList.indexof(2));
console.log(linkedList.removeAt(0));
console.log(linkedList.indexof("2"));
linkedList.println();


</script>
</head>
